// @test(3,[[0,1],[0,2],[2,1],[1,2],[1,0],[2,0]],5)=11
// @algorithm @lc id=1000063 lang=javascript
// @title chuan-di-xin-xi
/**
 * @param {number} n
 * @param {number[][]} relation
 * @param {number} k
 * @return {number}
 */
var numWays = function (n, relation, k) {
  const m = relation.length;
  const path = [];
  const backtrack = (code) => {
    if (path.length === k) {
      // 满足条件，更新答案
      if (code === n - 1) ans++;
      return;
    }
    for (let i = 0; i < m; i++) {
      let [a, b] = relation[i];
      if (a !== code) continue;
      // 选择下一个编号
      path.push(b);
      // 递归
      backtrack(b);
      // 取消选择
      path.pop();
    }
  };
  let ans = 0;

  backtrack(0);

  return ans;
};
